package com.demo.java.OD451_500.OD490;

import java.util.Scanner;
import java.util.*;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【最大花费金额(B卷-100分)】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/146423902
 */
public class OdMain {
    public static List<List<Integer>> combines = new ArrayList<>();  // 存储所有的三商品组合
    public static List<Integer> combine = new ArrayList<>(3);  // 当前的商品组合
    public static int res = -1;  // 记录最大总价，初始为 -1

    public static void main(String[] args) {
        // 处理输入
        Scanner in = new Scanner(System.in);
        String[] goods = in.nextLine().split(",");  // 商品价格字符串，按逗号分隔
        int r = in.nextInt();  // 用户的购物预算

        int[] goodsPrices = new int[goods.length];
        for (int i = 0; i < goods.length; i++) {
            goodsPrices[i] = Integer.parseInt(goods[i]);  // 将字符串转换为整数
        }

        Arrays.sort(goodsPrices);  // 对商品价格进行排序

        // 检查商品数量和最小三件商品的价格总和是否超过预算
        if (goodsPrices.length < 3 || goodsPrices[0] + goodsPrices[1] + goodsPrices[2] > r) {
            System.out.println(-1);  // 若商品数量少于3件或最小三件商品和大于预算，返回 -1
            return;
        }

        // 通过回溯法获取所有三商品组合
        takeGoods(goodsPrices, 0);

        // 对所有组合的总价进行排序，并找出符合预算条件的最大值
        combines.stream()
                .map(list -> sum(list))  // 计算每个组合的总和
                .sorted(Integer::compareTo)  // 对总和进行排序
                .forEach(sum -> {
                    if (sum > res && sum <= r) {  // 更新最大符合条件的总和
                        res = sum;
                    }
                });

        System.out.println(res);  // 输出结果
    }

    // 通过回溯法生成所有三商品的组合
    public static void takeGoods(int[] goodsPrices, int start) {
        if (combine.size() == 3) {  // 当选取了三个商品时，将其添加到结果集合
            combines.add(new ArrayList<>(combine));
            return;
        }
        for (int i = start; i < goodsPrices.length; i++) {
            combine.add(goodsPrices[i]);
            takeGoods(goodsPrices, i + 1);  // 递归生成组合
            combine.remove(combine.size() - 1);  // 回溯，移除最后一个商品
        }
    }

    // 计算给定组合的总和
    public static Integer sum(List<Integer> prices) {
        int sum = 0;
        for (Integer i : prices) {
            sum += i;  // 累加每个商品的价格
        }
        return sum;
    }
}